算法刷题指南，来自GitHub 68.8k star的硬核算法教程

很多朋友害怕算法，其实大可不必，算法题无非就那几个套路，一旦掌握，就会觉得算法实在是太朴实无华且枯燥了！本文选自硬核算法教程《labuladong的算法小抄》，带你学习套路，把握各类算法问题的共性！数据结构是工具，算法是通过合适的工具解决特定问题的方法。对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增、删、查、改。那么该如何在力扣刷题呢？很多文章都会告诉你“按标签刷”“坚持下去”等。不说这些不痛不痒的话，直接给具体的建议。先刷二叉树先刷二叉树！！先刷二叉树！！这是我刷题一年的亲身体会，下图是 2019 年 10 月的提交截图：据我观察，大部分人对与数据结构相关的算法文章不感兴趣，而是更关心动态规划、回溯、分治等技巧。这是不对的，这些常考算法技巧在《labuladong的算法小抄》中都会有所涉及，到时候你就会发现，它们看起来高大上，但本质上就是一个多叉树遍历的问题，配合算法框架，并没有多难。

• 为什么要先刷二叉树呢？

因为二叉树是最容易培养框架思维的，而且大部分常考算法本质上都是树的遍历问题。

• 刷二叉树时看到题目没思路？

其实大家不是没思路，只是没有理解“框架”是什么。不要小看下面这几行代码，几乎所有二叉树的题目一套用这个框架就都出来了。

1void traverse(TreeNode root) {
2    // 前序遍历
3    traverse(root.left);
4    // 中序遍历
5    traverse(root.right);
6    // 后序遍历
7}

比如随便拿几道题的解法代码出来，这里不用管具体的代码逻辑，只看看框架在其中是如何发挥作用的。 LeetCode 124 题 ，难度为 Hard，求二叉树中最大路径和，主要代码如下：

1int ans = INT_MIN;
2int oneSideMax(TreeNode* root) {
3    if (root == nullptr) return 0;
4
5    int left = max(0, oneSideMax(root->left));
6    int right = max(0, oneSideMax(root->right));
7
8    /**** 后序遍历 ****/
9    ans = max(ans, left + right + root->val);
10    return max(left, right) + root->val;
11    /****************/
12}

你看，这不就是后序遍历嘛。那为什么是后序呢？题目要求最大路径和，对于一个二叉树节点，是不是先计算左子树和右子树的最大路径和，然后加上自己的值，这样就得出新的最大路径和了？所以说这里就要使用后续遍历框架。 LeetCode 105 题 ，难度为 Medi um，要求根据前序遍历和中序遍历的结果还原一棵二叉树，这是很经典的问题，主要代码如下：

1TreeNode buildTree(int[] preorder, int preStart, int preEnd, 
2    int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
3
4    if(preStart > preEnd || inStart > inEnd) return null;
5
6    /**** 前序遍历 ****/
7    TreeNode root = new TreeNode(preorder[preStart]);
8    int inRoot = inMap.get(root.val);
9    int numsLeft = inRoot - inStart;
10    /****************/
11
12    root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, 
13                          inorder, inStart, inRoot - 1, inMap);
14    root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, 
15                          inorder, inRoot + 1, inEnd, inMap);
16    return root;
17}

不要看这个函数的参数很多，它们只是为了控制数组索引而已，本质上该算法就是一个前序遍历算法。 LeetCode 99 题 ，难度为 Hard，要求恢复一棵 BST（完全二叉树），主要代码如下：

1void traverse(TreeNode* node) {
2    if (!node) return;
3
4    traverse(node->left);
5
6    /****中序遍历 ****/
7    if (node->val < prev->val) {
8        s = (s == NULL) ? prev : s;
9        t = node;
10    }
11    prev = node;
12    /****************/
13
14    traverse(node->right);
15}

这不就是中序遍历嘛，对于一棵 BST，中序遍历意味着什么，应该不需要解释了吧。你看，Hard 难度的题目不过如此，而且还这么有规律可循，只要把框架写出来，然后往相应的位置加内容就行了，这不就是思路嘛！对于一个理解二叉树的人来说，刷一道二叉树的题目花不了多长时间。那么如果你对刷题无从下手或者有畏惧心理，不妨从二叉树下手，前 10 道也许有点难受；结合框架再做 20 道题，也许你就有点自己的理解了；刷完整个专题，再去做什么回溯、动态规化、分治专题，你就会发现只要涉及递归的问题，基本上都是树的问题。▽▽▽再举些例子吧。在《labuladong的算法小抄》“动态规划解题套路框架”章节中，会讲到凑零钱问题，暴力解法就是遍历一棵 N 叉树：

1def coinChange(coins: List[int], amount: int):
2
3    def dp(n):
4        if n == 0: return 0
5        if n < 0: return -1
6
7        res = float('INF')
8        for coin in coins:
9            subproblem = dp(n - coin)
10            # 子问题无解，跳过
11            if subproblem == -1: continue
12            res = min(res, 1 + subproblem)
13        return res if res != float('INF') else -1
14
15    return dp(amount)

这么多代码看不懂怎么办？直接提取框架，这样就能看出核心思路了，这就是刚才说到的遍历 N 叉树的框架：

1def dp(n):
2    for coin in coins:
3        dp(n - coin)

其实很多动态规划问题就是在遍历一棵树，你如果对树的遍历操作烂熟于心，那么起码知道怎么把思路转化成代码，也知道如何提取别人解法的核心思路。再看看回溯算法，在《labuladong的算法小抄》“回溯算法解题套路框架”中会直接告诉你，回溯算法就是一个 N 叉树的前序 + 后序遍历问题，没有例外。比如，排列组合问题、经典的回溯问题，主要代码如下：

1void backtrack(int[] nums, LinkedList<Integer> track) {
2    if (track.size() == nums.length) {
3        res.add(new LinkedList(track));
4        return;
5    }
6
7    for (int i = 0; i < nums.length; i++) {
8        if (track.contains(nums[i]))
9            continue;
10        track.add(nums[i]);
11        // 进入下一层决策树
12        backtrack(nums, track);
13        track.removeLast();
14    }
15
16/* 提取 N叉树遍历框架 */
17void backtrack(int[] nums, LinkedList<Integer> track) {
18    for (int i = 0; i < nums.length; i++) {
19        backtrack(nums, track);
20}

N 叉树的遍历框架，找出来了吧。你说，树这种结构重不重要？综上所述，对于畏惧算法或者刷题很多但依然感觉不得要领的朋友来说，可以先刷树的相关题目，试着从框架看问题，而不要纠结于细节。
所谓纠结细节，就比如纠结 i 到底应该加到 n 还是加到 n - 1 ，这个数组的大小到底应该开成 n 还是 n + 1 ？从框架看问题，就是像我们这样基于框架进行抽取和扩展，既可以在看别人解法时快速理解核心逻辑，也有助于我们找到自己写解法时的思路方向。当然，如果细节出错，你将得不到正确的答案，但是只要有框架，再错也错不到哪去，因为你的方向是对的。但是，你要是心中没有框架，那么根本无法解题，给你答案，也不能意识到这就是树的遍历问题。框架思维是很重要的，有时候按照流程写出解法，说实话我自己都不知道为啥是对的，反正它就是对了……这就是框架的力量，能够保证你在思路不那么清晰的时候，依然写出正确的程序。—— ——
最后我们总结一下，刷算法题建议从“树”分类开始刷，结合框架思维，把几十道题刷完，对于树结构的理解应该就到位了。这时候去看回溯、动态规划、分治等算法专题，对思路的理解可能会更加深刻一些。在思考问题的过程中，少纠结细节，不要热衷于炫技；希望读者多从框架看问题，多学习套路，把握各类算法问题的共性，《labuladong的算法小抄》将会为你提供这方面的帮助。图书推荐▊《labuladong的算法小抄》

付东来（@labuladong） 著

• GitHub 68.8k star的硬核算法教程

• labuladong带你挑战力扣算法题

• 挑战BAT等大厂Offer

本书专攻算法刷题，训练算法思维，应对算法笔试。注重用套路和框架思维解决问题，以不变应万变。

（扫码了解本书详情）

如果喜欢本文欢迎 在看丨留言丨分享至朋友圈 三连

 热文推荐  

---

▼点击阅读原文，获取本书详情~